package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/4/23
 * @description <a href="https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 */
public class Leetcode153_寻找旋转排序数组中的最小值 {
    /**
     * 采用二分搜索思想
     * 在nums[l,r]范围内查找,找到数组的中点mid,比较mid与r位置的元素的大小
     * - 如果nums[mid]>nums[r],则最小值一定在mid的右侧,丢弃左半部分,在右半部分继续查找
     * - 如果nums[mid]<nums[r],则最小值一定在mid的左侧,丢弃右半部分,在左半部分继续查找
     * 当区间内仅剩一个元素时,返回该元素,即为最小值
     * <p>
     * 时间复杂度O(logN) 二分搜索
     * 空间复杂度O(1)
     */
    public int findMin(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            throw new IllegalArgumentException("invalid input!");
        }

        //二分查找
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {  //终止条件:区间内仅剩一个元素
            //找到数组的中点mid,比较mid与r位置的元素的大小
            int mid = l + ((r - l) >> 1);

            if (nums[mid] > nums[r]) {  //nums[mid]>nums[r],则最小值一定在mid的右侧,丢弃左半部分,在右半部分继续查找
                l = mid + 1;
            } else { //nums[mid]<nums[r],则最小值一定在mid的左侧,丢弃右半部分,在左半部分继续查找
                r = mid;
            }
        }

        //区间内仅剩一个元素,返回该元素
        return nums[l];
    }
}
